Secondo alcune fonti un primo edificio di culto venne eretto tra il VII e l'VIII secolo dai monaci colombaniani di San Colombano, sul luogo dove verrà in seguito eretto il presbiterio della chiesa settecentesca. La prima citazione ufficiale della chiesa è presente in un antico documento datato al 6 giugno del 1198. La primitiva chiesa fu costruita in stile preromanico e divenne rettoria indipendente dalla pieve di Santa Maria Assunta di Voltri alla quale rimase legata fino al 1630. L'edificio subì nel 1349 il primo significativo ampliamento, raddoppiandone la superficie e spostando sul lato ovest l'originale facciata.

 

Due secoli dopo - tra il 1584 e il 1585 - si procedette con un nuovo lavoro di ampliamento allungando posteriormente il corpo della struttura ed elevando, oltre la metà del lato settentrionale, un nuovo campanile a sostituzione del precedente demolito in parte anni prima; la nuova chiesa fu consacrata l'11 settembre del 1594 dall'arcivescovo di Genova Alessandro Centurione.

 

Già elevata al titolo di chiesa parrocchiale - intitolata ai martiri Nazario e Celso - fu nel 1630 eletta ad arcipretura autonoma e sede di vicariato foraneo.

 

A seguito del conflitto bellico tra la Repubblica di Genova e il Piemonte si dovette nel 1672 fortificare l'area del tempio con due baluardi di cannoni e nel 1691 si decise di intraprendere un nuovo ampliamento della struttura, ma per mancanza di fondi l'idea dovette essere scartata; dodici anni dopo, nel 1703, fu ripresentata la proposta di una nuova costruzione secondo i canoni e gli stili architettonici dell'epoca. Fu scelto il progetto dell'architetto Antonio Maria Ricca il Vecchio, già autore del santuario della Madonnetta di Genova, e la direzione dei lavori (la prima pietra fu posizionata il 16 dicembre dello stesso anno) fu affidata al fratello Giovanni Antonio e in seguito a Giacomo Viano; quest'ultimo dovette inoltre sostituire lo stesso architetto Ricca poiché dopo la morte della moglie, avvenuta sul finire del Seicento, si ritirò in convento presso i Padri Agostiniani Scalzi del capoluogo ligure assumendo il nome di Padre Marino.

 

I lavori complessivamente terminarono il 12 dicembre del 1717, l'atrio e i due campanili furono invece finiti nel 1720, e la nuova chiesa in stile barocco fu solennemente consacrata il 28 ottobre del 1771. La struttura subì gravi danneggiamenti nel corso della seconda guerra mondiale, specie nel pesante bombardamento aereo compiuto il 14 agosto del 1944; le bombe rasero al suolo l'intera copertura, la volta affrescata, il pavimento policromo e alcune opere interne. I lavori di ricostruzione furono avviati nel 1946 con l'intento di riportare l'edificio di culto all'originale struttura barocca del Settecento; il 16 maggio del 1948 fu completata l'intera copertura della chiesa, mentre negli anni a seguire fu rifatta la volta ellittica in mattoni con le precedenti raffigurazioni affrescate.

 

All'interno sono presenti otto altari laterali in marmo dedicati a san Giuseppe e a sant'Erasmo, a san Lorenzo, a sant'Antonio abate, a san Giovanni Battista, alla Madonna del Rosario, alla Santissima Annunziata, a santa Lucia. Sopra l'altare maggiore è posizionato il crocifisso dello scultore genovese Anton Maria Maragliano e sono qui custodite le reliquie dei santi Nazario e Celso, santi patroni di Arenzano; il paliotto in marmo dell'altare è stato eseguito dagli scultori Daniele Solaro e Giovanni Tomaso Orsolino nel 1632 e consacrato il 23 agosto 1957 dal cardinale e arcivescovo di Genova Giuseppe Siri.

 

La volta è stata affrescata dal pittore Francesco Semino nel 1866 e raffigura al centro la scena dell'Ascensione, mentre nei sottostanti riquadri laterali sono raffigurate scene ed episodi della vita di Gesù quali la Risurrezione di Lazzaro, la Disputa al Tempio, Ecce Homo e Tu es Petrus. Sempre dello stesso pittore è l'opera ritraente L'Annunciazione dipinta nella lunetta sopra la balaustra del presbiterio e L'Ultima Cena sulla volta dell'atrio; l'opera è stata in seguito rieseguita negli anni ottanta dai pittori Mauro Repetto e Angelo Petrucci. Entrando nell'edificio, a sinistra, è invece presente un dipinto di Orazio De Ferrari ritraente la Madonna porgente il Bambino a san Felice da Cantalice.

 

Il presbiterio è stato invece affrescato dal pittore Ernesto Massiglio negli anni sessanta raffigurante la Gloria dei santi e sempre del Massiglio è l'opera ritraente lo Sbarco a Genova dei santi Nazario e Celso nel catino absidale. Il pulpito marmoreo è risalente alla fine del XIX secolo.

 

La struttura è corredata inoltre da ampie vetrate colorate ritraenti i santi Nazario e Celso, san Giovanni Battista, santa Caterina da Genova, san Bartolomeo, san Martino di Tours, santa Chiara di Assisi, san Pietro e san Sebastiano.

 

L'attuale colorazione esterna giallo ocra è stata eseguita negli anni novanta assieme al completo rifacimento del sagrato utilizzando il ciottolato monocromatico bianco e nero (lo stile è denominato come "risseu" nell'idioma ligure), utilizzato in diversi edifici di culto della Liguria.